The present invention relates to an elliptic-curve arithmetic method and an apparatus therefor and, more particularly, to an apparatus and method for implementing information security techniques (elliptic-curve cryptosystem/signature, factoring) and a recording medium having recorded thereon a program for implementing the method.
Elliptic-curve cryptosystems are now receiving attention as next-generation cryptosystems that will assume a key role in an era of electronic commerce, because they achieve the same level of security as do presently dominating cryptosystems but with a far shorter key length. However, conventional elliptic-curve cryptosystems have some problems in the processing speed for encryption and decryption and in the security level, and much study has been made for higher processing speed and for a higher level of security all over the world.
In the implementation of a public key cryptography or digital signature scheme over an elliptic curve, the processing time is mostly spent on m-multiplications over the elliptic curve. In general, the cryptography or signature scheme uses an elliptic curve defined over a finite field GF(q). Let the defined elliptic curve be represented by E/GF(q), where q is a prime or any power of a prime. In many of conventional mounting methods a prime or 2n (n is one or greater integer) is used as q.
It is possible to define an addition and a doubling for a point P over the elliptic curve. These addition and doubling will hereinafter be referred to as xe2x80x9celliptic curve additionxe2x80x9d and xe2x80x9celliptic curve doublingxe2x80x9d in distinction from ordinary additions and doublings. Of points over the elliptic curve, the identity element of addition will be represented by O. It is customary in the art to construct the m-multiplications (m is 2 or greater integer) by the combined use of the xe2x80x9celliptic curve additionxe2x80x9d and the xe2x80x9celliptic curve doubling.xe2x80x9d In this specification, the GF(q)-rational point refers to that one of points defined over an elliptic curve whose coordinates are expressed by the element of GF(q).
In some cases, a xe2x80x9cFrobenius mapxe2x80x9d may also be used to compute the m-multiplications. This scheme will hereinafter be called a xe2x80x9cbase-xcfx86 expansion method. Goblitz et al. have proposed a method for m-multiplying a GF(2k)-rational point (k is 2 or greater integer) over the elliptic curve E/GF(2) defined over the finite field GF(2). As described below, however, this method accelerates the multiplication only when q is very small.
Next, a description will be given of the elliptic curve and the Frobenius map.
Let F/GF(q) denote an elliptic curve defined over the finite field GF(q). For a group E(GF(qk)) of GF(qk)-rational points over E/GF(q), it is possible to define the multiplication using such a Frobenius map p as mentioned below.
Definition 1 (Frobenius Map)
The Frobenius map is defined by an endomorphism as
xcfx86: (x, y)xe2x86x92(xq, yq)
for a point P=(x, y), where x, yxcex5EGF(q)xe2x80x2, on the elliptic curve. GF(q)xe2x80x2 is an algebraic closure of GF(q).
The Frobenius map xcfx86 is an endomorphism over the elliptic curve. Letting m-multiplied map Pxe2x86x92mP be represented by [[m]], it satisfies the following equation:
xcfx862xe2x88x92[[t]]xcfx86+[[q]]=[[0]], xe2x88x922{square root over (q)} less than t less than 2{square root over (q)}xe2x80x83xe2x80x83(1)
Equation (1) has an imaginary root and permits a multiplication different from [[m]] with xcfx86. xcfx86 is a value that is determined uniquely to a given elliptic curve, and it can be calculated by known methods.
The calculation of the Frobenius map can usually be conducted faster than the elliptic curve addition. For example, in the case of representing an element of GF(qk) by using a normal basis, the Frobenius map can be computed only by the element replacement and the computing time is negligible.
Let xcex1 denote a generator of the normal basis. In the normal basis representation, an element axcex5EGF(qk) is represented by a=[a0, a1, . . . , ak-1] using aixcex5EGF(q) which provides                     a        =                              ∑                          i              =              0                                      k              -              1                                ⁢                      xe2x80x83                    ⁢                                    a              i                        ⁢                          α              qi                                                          (        2        )            
At this time, aq=[akxe2x88x921, a0, a1, . . . , akxe2x88x922], and the map xcfx86 can be applied by the element replacement.
In the base-xcfx86 expansion method, the first step is to transform mP using xcfx86 as follows:                     mP        =                              ∑                          i              =              0                        r                    ⁢                      xe2x80x83                    ⁢                                    c              i                        ⁢                          φ              i                        ⁢            P                                              (        3        )            
where xe2x88x92q less than ci less than q and r≅k.
Koblitz presented an m-multiplication algorithm for GF(2k))-rational points over E/GF(2) through utilization of the base-xcfx86 expansion method (N. Koblitz. xe2x80x9cCM-Curves with Good Cryptographic Properties,xe2x80x9d CRYPTO"" 91, pp.279-287 (1991)). And, Solinas proposed an improved version of the algorithm (J. A. Solinas, xe2x80x9cAn Improved Algorithm for Arithmetic on a Family of Elliptic Curves,xe2x80x9d CRYPTO"" 97, pp.357-371 (1997)). With these algorithms, xe2x88x921xe2x89xa6ci1 and the m-multiplication can be computed by a maximum of r Frobenius map calculations and elliptic curve additions.
For example, on the elliptic curve E/GF(2):y2+xy=x3+1, it can be regarded that xcfx86=[[(xe2x88x921+{square root over (xe2x88x927)})/2]]. In the case of obtaining 9P without using the base-xcfx86 expansion method, the following equation is used:
9P=(2xc3x972xc3x972+1)Pxe2x80x83xe2x80x83(4)
The calculation of Equation (4) requires three xe2x80x9celliptic curve doublingsxe2x80x9d and one xe2x80x9celliptic curve additionxe2x80x9d (a total of four computations).
On the other hand, the use of xcfx86 provides the following equation:
9P=(xcfx865xe2x88x92xcfx863+1)Pxe2x80x83xe2x80x83(5)
The calculation of Equation (5) can be conducted by two xe2x80x9celliptic curve additionsxe2x80x9d since the calculation of xcfx865P and xcfx863P takes negligible time. Hence, the computational time can be made shorter than in the case of using Equation (3).
Conventionally, a fast algorithm by the base-xcfx86 expansion method is applied mainly to elliptic curves defined over GF(qk) for a small integer q, but theoretically, it can be applied in more general cases. In such an instance, however, since the coefficient ci in Equation (3) becomes 0xe2x89xa6|ci| less than q, the operating time for the ci-multiplication is not negligible when q in GF(qk) is large. For instance, in Equation (5) in the prior art example, |ci| is 0 or 1 and the operating time for the ci-multiplication is negligible.
In this instance, the conventional method, if used intact, is not always faster than the method which does not use xcfx86. That is why the base-xcfx86 expansion method has been applied only when q is small.
It is an object of the present invention to provide an arithmetic method which permits m-multiplication over an elliptic curve defined over a finite field GF(qk) by the base-xcfx86 expansion method irrespective of the magnitude of a prime q, and apparatus for implementing the arithmetic method and a recording medium having recorded thereon a program for implementing the method,
According to the present invention, there is provided an elliptic-curve arithmetic method for m-multiplying a rational point P over an elliptic curve E/GF(q) defined over a finite field, the method comprising the steps of:
inputting a rational point P, a Frobenius map xcfx86 defined over the elliptic curve E/GF(q), an integer k and a prime q equal to or greater than 3 by input means;
calculating integers r and ci which satisfy the following equation, by using the Frobenius map xcfx86  m  =            ∑              i        =        0                    r        -        1              ⁢          xe2x80x83        ⁢                  c        i            ⁢              φ        i            
xe2x80x83where 0xe2x89xa6i less than r, 0xe2x89xa6rxe2x89xa6k and xe2x88x92qxe2x89xa6c1xe2x89xa6q;
calculating the following r points P0 to Prxe2x88x921:
P0=P
P1=xcfx86P
P2=xcfx862P
:
Prxe2x88x921=xcfx86rxe2x88x921P
by generating means supplied with the rational point P and the integers r and ci;
calculating the following equation:   mP  =            ∑              i        =        0                    r        -        1              ⁢          xe2x80x83        ⁢                  c        i            ⁢              φ        i            ⁢      P      
by table reference addition means supplied with the r points P0 to Prxe2x88x921; and outputting the calculated mP by outputting means.